package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 找出 3 位偶数
 */

public class Code2094 {
    public static void main(String[] args) {
        int[] digits = {2, 1, 3, 0};
        System.out.println(Arrays.toString(new Code2094().findEvenNumbers1(digits)));
    }

    public int[] findEvenNumbers(int[] digits) {

        int[] freq = new int[10];
        for (int digit : digits) {
            freq[digit]++;
        }

        List<Integer> result = new ArrayList<>();

        for (int num = 100; num < 1000; num += 2) {
            int[] tempFreq = Arrays.copyOf(freq, 10);
            int n = num;
            boolean valid = true;

            // 检查每一位数字是否可用
            for (int i = 0; i < 3; i++) {
                int digit = n % 10;
                if (tempFreq[digit] == 0) {
                    valid = false;
                    break;
                }
                tempFreq[digit]--;
                n /= 10;
            }

            if (valid && num / 100 != 0) { // 确保没有前导零
                result.add(num);
            }
        }

        // 转换为数组
        int[] answer = new int[result.size()];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = result.get(i);
        }

        return answer;
    }


    public int[] findEvenNumbers1(int[] digits) {
        int[] cnt = new int[10];
        for (int d : digits) {
            cnt[d]++;
        }

        List<Integer> ans = new ArrayList<>();
        dfs(0, 0, cnt, ans);
        return ans.stream().mapToInt(i -> i).toArray();
    }

    // i=0 百位，i=1 十位，i=2 个位，x 表示当前正在构造的数字
    private void dfs(int i, int x, int[] cnt, List<Integer> ans) {
        if (i == 3) {
            ans.add(x);
            return;
        }
        for (int d = 0; d < 10; d++) {
            if (cnt[d] > 0 && (i == 0 && d > 0 || i == 1 || i == 2 && d % 2 == 0)) {
                cnt[d]--; // 消耗一个数字 d
                dfs(i + 1, x * 10 + d, cnt, ans);
                cnt[d]++; // 复原
            }
        }
    }
}
